Lambda the Ultimate

Frege's Contribution to Philosophy of Language. Richard G. Heck and Robert May. Forthcoming in the Oxford Handbook of Philosophy of Language, edited by E. Lepore and B. Smith.

An investigation of Frege's various contributions to the study of language, focusing on three of his most famous doctrines: that concepts are unsaturated, that sentences refer to truth-values, and that sense must be distinguished from reference.

Warning: This isn't directly related to programming languages. In fact, if you haven't studied Frege this paper might be quite puzzling.

While not directly programming language related, I still think this paper might be of interest. Frege is quite an important figure in the history of logic, of course, and as we all know logic and computation are very much related to each other.

In addition, this paper deals with the notions of function and predicate, and these notions are part of our standard terminology. Reading this paper might improve our understanding of these notions and their history, as well as the notions of equality vs. identity, and intensional vs. extensional view of functions (see the end of section 4).

So if Java is a victory for Smalltalk’s implementation choices, and Ruby is a victory for Smalltalk’s language choices, what do you do if you want both? There’s still only one option: use Smalltalk.

You be the judge.

Stefan Holdermans. Master's thesis, Utrecht University, 2005.
An extension of Wadler's views.

In the conclusion, in a comparison to SYB, this paper notes:

Even when they target the same types of applications, it is often hard to transfer ideas and techniques between two different [generic programming] approaches. Therefore, frameworks for generic programming are typically studied in rather isolated environments. When proposals are compared to one another, the focus usually is on issues like which programs can and which programs cannot be written within the context of a specific paradigm: attention is drawn to the surface area of a generic-programming model, rather than to the underlying theory and techniques.

Generic views on data types may allow us to break with this tradition and incorporate different approaches within a single framework. The idea is to define a view that captures the way in which a given approach treates data types and to consequently transfer the building blocks of that approach to Generic Haskell idioms.

Before noting the impossibility of even this approach to encode generic fold.

Module Mania: A Type-Safe, Separately Compiled, Extensible Interpreter

To illustrate the utility of a powerful modules language, this paper presents the embedded interpreter Lua-ML. The interpreter combines extensibility and separate compilation without compromising type safety. Its types are extended by applying a sum constructor to built-in types and to extensions, then tying a recursive knot using a two-level type; the sum constructor is written using an ML functor. The initial basis is extended by composing initialization functions from individual extensions, also using ML functors.

This is an excellent example of how the ML module language doesn't merely provide encapsulation but also strictly adds expressive power. It also demonstrates how a dynamic language (Lua) can be embedded in the statically-typed context of ML. Finally, it demonstrates that none of this need come at the expense of separate compilation or extensibility. Norman Ramsey's work is always highly recommended.

Classic Java

This collection is an implementation of (most of) ClassicJava, as defined
in "A Programmer's Reduction Semantics for Classes and Mixins," by Matthew
Flatt, Shriram Krishnamurthi, and Matthias Felleisen; in _Formal Syntax and
Semantics of Java_, Springer-Verlag LNCS 1523, pp. 241-269, 1999. A
tech-report version of the paper is also available at
<http://www.ccs.neu.edu/scheme/pubs/#tr97-293. The implementation is
written in PLT Redex, also available through PLaneT. Please consult that
package's documentation for further details.

This might be interesting to folks curious about how to formalize a real language, or about how PLT Redex works in practice.

The workshop on Synchronization and Concurrency in Object-Oriented Languages has a nice, accessible collection of papers on software transactional memory and other language-based approaches to building concurrent systems.

Fusion in less space. Catherine Hope and Graham Hutton

In functional programming, programs are often written in a compositional style. There are many advantages to this, such as clarity and modularity, but the resulting programs can be inefficient in terms of space, due to the use of intermediate data structures. These structures may be removed using deforestation techniques, but whether the space performance is actually improved depends on the structures being consumed in the same order that they are produced. In this paper we explore this problem and suggest a solution, in particular for lists and then generalising to trees.

Since the paper discusses many examples, it is quite enjoyable to read and can even serve as an introduction to folds.

Metaphors attempts to address four topics essential to software development that are traditionally handled outside of the programming language. The first is support for distributed runtime environment, which I just talked about. The other three are (a) support for contextual programming, (b) support for autonomous executable entities, and (c) support for software evolution and reuse.

I am not sure what to make of this.

Generic programming — Or: write everything once

Ralf Hinze summarizes polytypic programming, with a focus on Generic Haskell. He discusses:

• Generic functions on types
• Generic functions on type constructors
• Generic types

In addition to the usual generic equality and serialization, he mentions fold and map (though not by name), along with a dozen other ideas that use polytypism. He also notes that the Generic Haskell experiment will be continued and integrated into a "standard Haskell compiler".

(via lemonodor)

A collection of links to Lisp books available online.